On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:
"G": go straight 1 unit;"L": turn 90 degrees to the left;"R": turn 90 degrees to the right.
The robot performs the instructions given in order, and repeats them forever.
Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.
Example 1:
Input: instructions = "GGLLGG" Output: true Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0). When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
Example 2:
Input: instructions = "GG" Output: false Explanation: The robot moves north indefinitely.
Example 3:
Input: instructions = "GL" Output: true Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
Constraints:
1 <= instructions.length <= 100instructions[i]is'G','L'or,'R'.
Average Rating: 4.47 (89 votes)
Solution
Overview
The robot's trajectory attractor is a set of trajectories toward which a system tends to evolve. The question may sound a bit theoretical - is this attractor is limited or not. In other words, if there exists a circle in the plane such that the robot never leaves the circle.
| Diverging Trajectory | Limit Cycle Trajectory |
|---|---|
![]() |
![]() |
Figure 1. Diverging Trajectory vs Limit Cycle Trajectory.
Why is it interesting to know? There is a bunch of practical problems related to topology, networks planning, and password brute-forcing. For all these problems, the first thing to understand is do we work within a limited space or the behavior of our system could drastically diverge at some point?
| Diverging Trajectory | Limit Cycle Trajectory |
|---|---|
![]() |
![]() |
Figure 2. Diverging Trajectory vs Limit Cycle Trajectory.
Draw some trajectories
Here is a Jupiter notebook used to draw all figures in this article. Do not hesitate to play with it in local or on the online platforms. Drawing different trajectories might help to notice some patterns.
Approach 1: One Pass
Intuition
This solution is based on two facts about the limit cycle trajectory.
- After at most 4 cycles, the limit cycle trajectory returns to the initial point
x = 0, y = 0. That is related to the fact that 4 directions (north, east, south, west) define the repeated cycles' plane symmetry [proof].
| Ex. 1: Trajectory 1 | Ex. 2: Trajectory 2 |
|---|---|
![]() |
![]() |
Figure 3. After 4 cycles the limit cycle trajectory returns to the initial point x = 0, y = 0.
-
We do not need to run 4 cycles to identify the limit cycle trajectory. One cycle is enough. There could be two situations here.
-
First, if the robot returns to the initial point after one cycle, that's the limit cycle trajectory.
-
Second, if the robot doesn't face north at the end of the first cycle, that's the limit cycle trajectory. Once again, that's the consequence of the plane symmetry for the repeated cycles [proof].
-
| Ex. 1: Trajectory 1 | Ex. 2: Trajectory 2 |
|---|---|
![]() |
![]() |
Figure 4. If at the end of one cycle the robot doesn't face north, that's the limit cycle trajectory.
Algorithm
-
Let's use numbers from 0 to 3 to mark the directions:
north = 0,east = 1,south = 2,west = 3. In the arraydirectionswe could store corresponding coordinates changes, i.e.directions[0]is to go north,directions[1]is to go east,directions[2]is to go south, anddirections[3]is to go west. -
The initial robot position is in the center
x = y = 0, facing northidx = 0. -
Now everything is ready to iterate over the instructions.
-
If the current instruction is
R, i.e. to turn on the right, the next direction isidx = (idx + 1) % 4. Modulo here is needed to deal with the situation - facing west,idx = 3, turn to the right to face north,idx = 0. -
If the current instruction is
L, i.e. to turn on the left, the next direction could written in a symmetric wayidx = (idx - 1) % 4. That means we have to deal with negative indices. A more simple way is to notice that 1 turn to the left = 3 turns to the right:idx = (idx + 3) % 4. -
If the current instruction is to move, we simply update the coordinates:
x += directions[idx][0],y += directions[idx][1].
-
-
After one cycle we have everything to decide. It's a limit cycle trajectory if the robot is back to the center:
x = y = 0or if the robot doesn't face north:idx != 0.
Implementation
Complexity Analysis
-
Time complexity: O(N), where N is a number of instructions to parse.
-
Space complexity: O(1) because the array
directionscontains only 4 elements.
Appendix: Mathematical Proof
Let's provide a strict mathematical proof.
If the robot doesn't face north at the end of the first cycle, then that's the limit cycle trajectory.
First, let's check which direction the robot faces after 4 cycles.
Let's use numbers from 0 to 3 to mark the directions:
north = 0, east = 1, south = 2, west = 3.
After one cycle the robot is facing direction k != 0.
After 4 cycles, the robot faces direction (k * 4) % 4 = 0, i.e.
after 4 cycles, the robot is always facing north.
Second, let's find the robot coordinates after 4 cycles.
The robot initial coordinates are x = y = 0. After one cycle,
the new coordinates are x1=x+Δx, y1=y+Δy, where
both Δx and Δy could be positive or negative.
Let's consider four situations.
- After one cycle, the robot faces north.
Then here is what we have after 4 cycles:
x4=x+Δx+Δx−Δx+Δx=x+4Δx
y4=y+Δy+Δy+Δy+Δy=y+4Δy
- After one cycle, the robot faces east.
Then here is what we have after 4 cycles:
x4=x+Δx+Δy−Δx−Δy=x
y4=y+Δy−Δx−Δy+Δx=y
- After one cycle, the robot faces south.
Then here is what we have after 4 cycles:
x4=x+Δx−Δx+Δx−Δx=x
y4=y+Δy−Δy+Δy−Δy=y
- After one cycle, the robot faces west.
Then here is what we have after 4 cycles:
x4=x+Δx−Δy−Δx+Δy=x
y4=y+Δy+Δx−Δy−Δx=y
Hence, if the robot doesn't face north at the end of the first cycle, then after 4 cycles, the robot is back to the initial coordinates and faces north.
The following statement is a straight consequence.
After at most 4 cycles, the limit cycle trajectory returns to the initial point.
Last Edit: August 19, 2020 8:57 AM
finally I came up with one answer (not facing north or 0,0) by myself ...I feel smart right now...
It seems there is a typo at:
After one cycle, the robot faces north.
Then here is what we have after 4 cycles:
x4=x+Δx+Δx−Δx+Δx=x+4Δx
You probably meant x4=x+Δx+Δx (plus) Δx+Δx=x+4Δx
Is it an international Math olympiad ?...
Questions like these seems to present just to let your morale down...
January 27, 2021 5:40 PM
Just had this for Amazon online assessment. I played out four cycles and just checked to see if we were back at beginning. My updating of the direction was also a lot more verbose (didn't use modulus). And I was invited for onsite.
September 17, 2020 11:29 PM
I accidentally learned dynamical systems
December 22, 2020 11:21 PM
This is one of the stupidest interview questions I have seen so far...
September 18, 2020 5:00 AM
Nice question. It may be more readable to define dx and dy to represent velocity rather than using modulo.
class Solution {
public boolean isRobotBounded(String instructions) {
int x = 0;
int y = 0;
int dx = 0;
int dy = 1; // Initially face North.
for (int i = 0; i < instructions.length(); i++) {
char instruction = instructions.charAt(i);
if (instruction == 'G') {
x = x + dx;
y = y + dy;
} else if (instruction == 'L') {
int tmp = dy;
dy = dx;
dx = -tmp;
} else if (instruction == 'R') {
int tmp = dx;
dx = dy;
dy = -tmp;
}
}
return (x == 0 && y == 0) || dy != 1;
}
}
Last Edit: January 19, 2021 5:43 PM
Python Solution. Read Comments, You Will Understand for Sure.
# Solution 1: O(n) time complexity and o(1) space complexity
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
# initial poition
x = y = 0
# intially facing north
direction = 0
# 0 = north, 1 = east, 2 = south, 3 = west
# With a move (G) in any direction, you will go 1 unit.
# So you need to add 1 unit with x or y depending on
# which direction you are going. For example,
# if you go north from (x,y), then new position would be
# (x, y+1) which is you get by x = x+0, y = y+1.
# Now think about how you can get new position for other direction
# So creating a dictionary with directions as keys and the
# amount we need to add with x and y while we go for 1 unit
# as value.
possible_moves = {0: [0,1], 1: [1,0], 2: [0,-1], 3: [-1,0]}
# Now the idea is if after executing the instructions, if you
# get your final position at (0,0) or if you are not facing north
# direction, that means you will be in circle. Not facing north
# direction means, as you can repeat the instructions, if you are
# not facing north after 1st execution of the instructions, just
# repeat 3 more times of the same instructions, you will see
# yourself at the origin. Think about with 'GL' or 'GR'
# instructions as an example. With instruction 'GLGR', you
# can't be back at origin, no matter how many times you repeat.
for instruction in instructions:
# turing left means, you will get the same direction
# if you turn right 3 times. modulo beacuse we have
# only 4 directions to consider.
if instruction == 'L':
direction = (direction + 3)% 4
elif instruction == 'R':
direction = (direction + 1)% 4
# If we see 'G' means we need to go 1 unit and
# change x or y value according to the direction
# we are going. By this we will get new position.
else:
x = x + possible_moves[direction][0]
y = y + possible_moves[direction][1]
# Finally, if you get your final position at (0,0) or if you
# are not facing north direction, that means you will be
# in circle.
return (x==0 and y ==0) or direction !=0
September 17, 2020 10:46 PM
Great analysis. Is it a competitive programming question or interview question? This is a great question if one has a whiteboard during the physical onsite interview but it definitely is not a great question for virtual onsite or phone interview. I just hope that none gets a "smart" interviewer who happens to ask this question. Nevertheless, it is a fun question to practise.
April 5, 2021 6:26 AM
I would really like to know how many times an average software developer actually codes something like this, even at FAANG. I feel like we're raising the bar unnecessarily; and then end up having to PIP people out because they couldn't be application developers
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/25/2021 09:22 | Accepted | 0 ms | 6.2 MB | cpp |
| 05/25/2021 09:22 | Wrong Answer | N/A | N/A | cpp |
xxxxxxxxxx};class Solution {public: bool isRobotBounded(string instructions) { char dir = 'N'; int x = 0, y = 0; for(int i=0;i<instructions.size();i++) { char in = instructions[i]; if(in == 'G') { if(dir == 'N') x++; if(dir == 'E') y++; if(dir == 'S') x--; if(dir == 'W') y--; } else if(in == 'L') { if(dir == 'N') dir = 'W'; else if(dir == 'E') dir = 'N'; else if(dir == 'S') dir = 'E'; else dir = 'S'; } else if(in == 'R') { if(dir == 'N') dir = 'E'; else if(dir == 'E') dir = 'S'; else if(dir == 'S') dir = 'W'; else dir = 'N'; } } if(x == 0 && y == 0) return true; if(dir == 'N') return false; return true; }};







